package com.leetcode.test.tree;

import org.junit.Assert;
import org.junit.Test;

import java.util.*;

/**
 * 层次遍历介绍  https://leetcode-cn.com/explore/learn/card/data-structure-binary-tree/2/traverse-a-tree/8/
 */
public class 自己写的层次遍历2 {

    @Test
    public void test() {
        Node f = new Node('F');
        Node b = f.left = new Node('B');
        Node g = f.right = new Node('G');
        Node a = b.left = new Node('A');
        Node d = b.right = new Node('D');
        Node i = g.right = new Node('I');
        Node c = d.left = new Node('C');
        Node e = d.right = new Node('E');
        Node h = i.left = new Node('H');

        List<List<Character>> list = foo(f);

        Assert.assertEquals(
                Arrays.asList(Arrays.asList('F'), Arrays.asList('B', 'G'), Arrays.asList('A', 'D', 'I'), Arrays.asList('C', 'E', 'H')),
                list
        );
    }

    class Node {
        Node left;
        Node right;
        char val;

        public Node(char val) {
            this.val = val;
        }
    }


    List<List<Character>> foo(Node root) {
        if (root == null) {
            return new ArrayList<>();
        }

        List<List<Character>> doubleList = new ArrayList<>();
        Queue<List<Node>>     queue      = new ArrayDeque<>();
        queue.add(Arrays.asList(root));

        while (!queue.isEmpty()) {
            List<Node>      nodes          = queue.remove();
            List<Character> curLevelValues = new ArrayList<>();// 当前层的值
            List<Node>      nextLevelNodes = new ArrayList<>();// 下一层节点

            for (Node node : nodes) {
                curLevelValues.add(node.val);

                if (node.left != null) {
                    nextLevelNodes.add(node.left);
                }
                if (node.right != null) {
                    nextLevelNodes.add(node.right);
                }
            }

            if (nextLevelNodes.size() > 0) {
                queue.add(nextLevelNodes);
            }
            if (curLevelValues.size() > 0) {
                doubleList.add(curLevelValues);
            }
        }

        return doubleList;
    }

}
